#include <iostream>
#include <vector>
#include <chrono>
#include <random>
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct MillerRabin {
	using i128 = __int128;
	using i64 = long long;

	i64 power(i64 a, i64 b, i64 mod) {
		i64 result = 1;
		for (; b > 0; b >>= 1) {
			if (b & 1) {
				result = (i128)result * a % mod;
			}
			a = (i128)a * a % mod;
		}
		return result;
	}

	bool judge(i64 n) {
		if (n < 3 || !(n & 1)) {
			return (n == 2);
		}
		i64 u = n - 1, t = 0;
		while (!(u & 1)) {
			u /= 2;
			t++;
		}
		for (int i = 0, m = sizeof(ud_) / sizeof(int); i < m; i++) {
			i64 v = power(ud_[i], u, n);
			if (v <= 1 || v == n - 1) {
				continue;
			}
			for (int j = 1; j <= t; j++) {
				v = (i128)v * v % n;
				if (v == n - 1 && j != t) {
					v = 1;
					break;
				}
				if (v == 1) {
					return false;
				}
			}
			if (v != 1) {
				return false;
			}
		}
		return true;
	}

	int ud_[9] = {2, 325, 2047, 9375, 28178, 450775, 1373653, 9780504, 1795265022};
};
MillerRabin mr;
// O(klogp) k是ud的长度
int main() {
	
	return 0;
}